package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
 *
 * 如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
 *
 * 对数组 a 执行 按位或，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-15
 * Time:20:09
 */
public class DFS2044 {
    public int[] num;
    public int count = 0;
    public int maxI = 0;
    public int countMaxOrSubsets(int[] nums) {
        if(nums == null)return 0;
        this.num = nums;
        DFS(0,0);
        return count;
    }
    public void DFS(int pos,int o){
        if(pos == num.length){
            if(o > maxI){//最大的按位或值
                maxI = o;
                count = 1;
            }else if(o == maxI){
                count ++;
            }
            return;
        }
        DFS(pos + 1,o | num[pos]);//每一次都添加一个或的元素  先进行一次找到所有按位或的最大值
        DFS(pos + 1,o);//再进行一次找到所有的按位或的最大值子集队
    }
}
